﻿#define _CRT_SECURE_NO_WARNINGS 1

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param str string字符串
     * @return string字符串vector
     */
    vector<string> result;
    vector<int> exist;
    int n;
    void dfs(string& str, string res)
    {
        if (res.size() == n)
        {
            result.push_back(res);
            return;
        }

        for (int i = 0; i < n; ++i)
        {
            if (!exist[i])
            {
                if (i > 0 && str[i] == str[i - 1] && !exist[i - 1])//剪枝，相同的字母，并且只有当前面字母不选择的时候，后面相同的字母也不选择   
                    continue;
                exist[i] = 1;
                dfs(str, res + str[i]);
                exist[i] = 0;
            }
        }
    }
    vector<string> Permutation(string str)
    {
        n = str.size();
        exist.assign(n, 0);
        sort(str.begin(), str.end());//排序，让相同的字母靠在一起
        dfs(str, "");
        return result;
    }
};

/*
输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，
你可以以任意顺序返回这个字符串数组。
例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

数据范围：n<10
要求：空间复杂度O(n!)，时间复杂度O(n!)
输入描述：
输入一个字符串,长度不超过10,字符只包括大小写字母。

示例1
输入：
"ab"
返回值：
["ab","ba"]
说明：
返回["ba","ab"]也是正确的
*/

